template <class Key, class T, class Compare>
bool RBTreeRank<Key, T, Compare>::Less(const NodeBase *n1, const NodeBase *n2) const
{
    return rank_compare_(((const Node *)n1)->v, ((const Node *)n2)->v);
}

template <class Key, class T, class Compare>
void RBTreeRank<Key, T, Compare>::RBInsert(NodeBase *z)
{
    NodeBase *y = &nil_;
    NodeBase *x = root_;
    while (x != &nil_) {
        y = x;
        if (Less(z, x)) {
            x = x->left;
        } else {
            x = x->right;
        }
    }
    z->p = y;
    if (y == &nil_) {
        root_ = z;
    } else if (Less(z, y)) {
        y->left = z;
    } else {
        y->right = z;
    }
    z->left = &nil_;
    z->right = &nil_;
    z->color = RED;
    z->n = 0;
    TreeNFixup(z, 1);
    RBInsertFixup(z);
}

template <class Key, class T, class Compare>
auto RBTreeRank<Key, T, Compare>::Add(Key key, const T &v) -> std::pair<Iterator, bool>
{
    return Add(key, (T&&)T{v});
}

template <class Key, class T, class Compare>
auto RBTreeRank<Key, T, Compare>::Add(Key key, T &&v) -> std::pair<Iterator, bool>
{
    auto rst = rank_objs_.emplace(key, nullptr);
    if (rst.second) {
        auto z = rst.first->second = new Node;
        z->v = std::move(v);
        z->key = key;
        RBInsert(z);
        return {{this, z}, true};
    } else {
        return {{this, rst.first->second}, false};
    }
}

template <class Key, class T, class Compare>
bool RBTreeRank<Key, T, Compare>::Remove(Key key)
{
    auto itr = rank_objs_.find(key);
    if (itr != rank_objs_.end()) {
        auto z = itr->second;
        RBDelete(z);
        rank_objs_.erase(itr);
        delete z;
        return true;
    } else {
        return false;
    }
}

template <class Key, class T, class Compare>
void RBTreeRank<Key, T, Compare>::Clear()
{
    for (auto &pair : rank_objs_) {
        delete pair.second;
    }
    rank_objs_.clear();
    root_ = &nil_;
}

template <class Key, class T, class Compare>
template <typename F>
auto RBTreeRank<Key, T, Compare>::Dirty(Key key, F &&f) -> std::pair<Iterator, int>
{
    auto itr = rank_objs_.find(key);
    if (itr != rank_objs_.end()) {
        Iterator itrx{this, itr->second};
        return {itrx, Dirty(itrx, std::move(f))};
    }
    return {end(), 0};
}

template <class Key, class T, class Compare>
template <typename F>
int RBTreeRank<Key, T, Compare>::Dirty(Iterator itr, F&& f)
{
    auto y = itr();
    auto hint = f(y->v);
    if (hint < 0) {
        auto x = TreePredecessor(y);
        if (x == &nil_ || Less(x, y)) {
            hint = 0;
        }
    } else if (hint > 0) {
        auto z = TreeSuccessor(y);
        if (z == &nil_ || Less(y, z)) {
            hint = 0;
        }
    }
    if (hint != 0) {
        RBDelete(y);
        RBInsert(y);
    }
    return hint;
}

template <class Key, class T, class Compare>
size_t RBTreeRank<Key, T, Compare>::GetRank(Key key) const
{
    auto itr = rank_objs_.find(key);
    if (itr != rank_objs_.end()) {
        return GetRank({this, itr->second});
    } else {
        return 0;
    }
}

template <class Key, class T, class Compare>
size_t RBTreeRank<Key, T, Compare>::GetRank(Iterator itr) const
{
    return TreeRank(itr()) + 1;
}

template <class Key, class T, class Compare>
auto RBTreeRank<Key, T, Compare>::find(Key key) const -> Iterator
{
    auto itr = rank_objs_.find(key);
    if (itr != rank_objs_.end()) {
        return {this, itr->second};
    } else {
        return end();
    }
}

template <class Key, class T, class Compare>
auto RBTreeRank<Key, T, Compare>::advance(size_t i) const -> Iterator
{
    return {this, (Node *)(root_ != &nil_ ? TreeAdvance(i) : &nil_)};
}

template <class Key, class T, class Compare>
auto RBTreeRank<Key, T, Compare>::begin() const -> Iterator
{
    return {this, (Node *)(root_ != &nil_ ? TreeMinimum(root_) : &nil_)};
}

template <class Key, class T, class Compare>
auto RBTreeRank<Key, T, Compare>::end() const -> Iterator
{
    return {this, (Node *)&nil_};
}

template <class Key, class T, class Compare>
size_t RBTreeRank<Key, T, Compare>::size() const
{
    return rank_objs_.size();
}

template <class Key, class T, class Compare>
bool RBTreeRank<Key, T, Compare>::empty() const
{
    return rank_objs_.empty();
}

template <class Key, class T, class Compare>
RBTreeRank<Key, T, Compare>::Iterator::Iterator(const RBTreeRank *rank, Node *node)
    : rank(rank), node(node) {}
template <class Key, class T, class Compare>
auto RBTreeRank<Key, T, Compare>::Iterator::operator++() -> Iterator & {
    node = (Node *)rank->TreeSuccessor(node); return *this;
}
template <class Key, class T, class Compare>
auto RBTreeRank<Key, T, Compare>::Iterator::operator--() -> Iterator & {
    node = (Node *)rank->TreePredecessor(node); return *this;
}
template <class Key, class T, class Compare>
auto RBTreeRank<Key, T, Compare>::Iterator::operator*() const -> const Node & {
    return *node;
}
template <class Key, class T, class Compare>
auto RBTreeRank<Key, T, Compare>::Iterator::operator->() const -> const Node * {
    return node;
}
template <class Key, class T, class Compare>
bool RBTreeRank<Key, T, Compare>::Iterator::operator==(Iterator other) const {
    return this->node == other.node;
}
template <class Key, class T, class Compare>
bool RBTreeRank<Key, T, Compare>::Iterator::operator!=(Iterator other) const {
    return this->node != other.node;
}
template <class Key, class T, class Compare>
auto RBTreeRank<Key, T, Compare>::Iterator::operator()() const -> Node * {
    return node;
}
